typedef struct BinarySearchNode
{
    BinarySearchNode *left;
    BinarySearchNode *right;
    const char *data;
} BinarySearchNode;

class BinarySearchTree
{

private:
    BinarySearchNode *root;
    int isBST(BinarySearchNode *node);
    int isBST(BinarySearchNode *node, const char *prev);
    int isBST(BinarySearchNode *node, const char *min, const char *max);
    BinarySearchNode *findMin(BinarySearchNode *node);
    BinarySearchNode *findMax(BinarySearchNode *node);
    BinarySearchNode *BST2DLL(BinarySearchNode *root, BinarySearchNode *ltail);
    BinarySearchNode *pruneBST(BinarySearchNode *node, const char *mindata, const char *maxdata);

public:
    BinarySearchTree(const char *data);
    BinarySearchNode *insertNode(const char *data);
    BinarySearchNode *find(const char *data);
    BinarySearchNode *findMin();
    BinarySearchNode *findMax();
    void remove(const char *data);
    int isBST();
    BinarySearchNode *BST2DLL();
    BinarySearchNode *pruneBST(const char *mindata, const char *maxdata);
};
